#!/usr/bin/python
# coding:utf-8
from __future__ import print_function


class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def pre_order_print(self):
        print(self.data, end='')
        if self.left is not None:
            self.left.pre_order_print()

        if self.right is not None:
            self.right.pre_order_print()


def getTrees(array, start, end):
    trees = []
    if end - start == 1:
        return [Node(data=array[start])]
    for x in range(start, end):
        leftTree = getTrees(array, start, x)
        rightTree = getTrees(array, x+1, end)
        for left, right in yield_left_right(leftTree, rightTree):
            root = Node(data=array[x], left=left, right=right)
            trees.append(root)
    return trees


def yield_left_right(left_trees, right_trees):
    if len(left_trees) == 0:
        left_trees = [None]
    if len(right_trees) == 0:
        right_trees = [None]
    for left_tree in left_trees:
        for right_tree in right_trees:
            yield left_tree, right_tree


if __name__ == '__main__':
    array = [0, 1, 2]
    trees = getTrees(array, 0, len(array))
    print(' size: ', len(trees))
    for tree in trees:
        tree.pre_order_print()
        print("")